#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

//——————哈希表闭散列线性探测实现——————————————

// 注意：假如实现的哈希表中元素唯一，即key相同的元素不再进行插入
// 为了实现简单，此哈希表中我们将比较直接与元素绑定在一起
namespace Close_Hash
{
	enum State { EMPTY, EXIST, DELETE };

	template<class K, class V>
	class HashTable
	{
		struct Elem
		{
			pair<K, V> _val;
			State _state;
		};
		
	public:
		HashTable(size_t capacity = 3)
			: _ht(capacity), _size(0), _totalSize(0)
		{
			for (size_t i = 0; i < capacity; ++i)
				_ht[i]._state = EMPTY;
		}

		// 插入
		bool Insert(const pair<K, V>& val)
		{
			// if (Find(val.first) != -1) return false; //存在就不插入，不用这个，因为会返回-1，会导致死循环

			size_t pos = HashFunc(val.first); //获取哈希地址
			CheckCapacity(); //检测是否需要扩容

			/*while (_ht[pos]._state == EXIST){
				++pos;
				pos %= _ht.size();
			}*/

			while (_ht[pos]._state != EMPTY)
			{
				if (_ht[pos]._state == EXIST && _ht[pos]._val.first == val.first)
				{ 
					// key已经存在
					return false;
				}

				// 发生哈希冲突,采用线性探测进行处理
				++pos;
				pos %= _ht.size();
			}
			
			_ht[pos]._state = EXIST;
			_ht[pos]._val = val;
			_size++;
			_totalSize++;
			return true;
		}

		// 查找
		int Find(const K& key)
		{
			size_t pos = HashFunc(key); //找到key对应位置
			while (_ht[pos]._state != EMPTY)
			{
				if (_ht[pos]._state == EXIST && _ht[pos]._val.first == key)
					return pos;
				
				//线性探测
				pos++;

				pos %= _ht.size();
			}
			return -1; //如果要返回-1,就需要把size_t改成int
		}

		// 删除
		bool Erase(const K& key)
		{
			int pos = Find(key);
			if (pos != -1) {
				_ht[pos]._state = DELETE;
				_size--;
				return true;
			}
			return false;
		}

		size_t Size()const
		{
			return _size;
		}

		bool Empty() const
		{
			return _size == 0;
		}

		void Swap(HashTable<K, V>& ht)
		{
			swap(_size, ht._size);
			swap(_totalSize, ht._totalSize);
			_ht.swap(ht._ht);
		}

	private:
		size_t HashFunc(const K& key)
		{
			return key % _ht.size();
		}

		void CheckCapacity()
		{// 遍历旧表， 将所有数据映射到新表
			// 负载因子达到70%以上时，扩容
			if (_totalSize * 10 / _ht.size() >= 7) 
			{
				//HashTable<K, V> newHT(GetNextPrime(_ht.capacity()));
				HashTable<K, V> newHT;
				newHT._ht.resize(_ht.size() * 2);
				
				for (size_t i = 0; i < _ht.size(); ++i)
				{
					if (_ht[i]._state == EXIST) {
						newHT.Insert(_ht[i]._val);
					}
				}
				this->Swap(newHT);
				//_ht.swap(newHT._ht);
			}
		}

	private:
		vector<Elem> _ht;
		size_t _size;
		size_t _totalSize;  // 哈希表中的所有元素：有效和已删除, 扩容时候要用到
	};
}

void TestHT1()
{
	Close_Hash::HashTable<int, int> ht;
	int a[] = { 11,21,4,14,24,15,9 };
	for (auto e : a)
	{
		ht.Insert({ e,e });
	}
	ht.Insert({ 19, 19 });
	ht.Insert({ 19,190 });

	cout << ht.Find(24) << endl;
	cout << ht.Find(4) << endl;
	ht.Erase(4);
	cout << ht.Find(24) << endl;
	cout << ht.Find(4) << endl;

	ht.Insert({ 4,4 });
}


int main()
{
	TestHT1();
	system("pause");
	return 0;
}

